package com.tree.leetcode.array;

import com.tree.leetcode.common.ListNode;

/**
 * @ClassName com.tree.leetcode.array
 * Description: <类功能描述>.
 * <br>
 * @Author frankzsliu
 * @Date 2024/2/3 13:57
 * @Version 1.0
 */
public class ReverseKGroup_25 {
    public static void main(String[] args) {

    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy;

        while (end.next != null){
            //1. 找到k的最后1个节点
            for(int i =0 ; i < k && end != null ; i++){
                end = end.next;
            }
            //2. 如果end为空， 则代表后面不足K个节点， 结束
            if(end == null ){
                break;
            }
            //3. 准备开始节点和翻转区间的后续节点
            // 获取 pre.next 的节点作为反转区间的起始节点 start
            ListNode start = pre.next;
            //获取end.next的节点作为翻转区间的后续节点
            ListNode restNode = end.next;
            //4. 将end.next 断开， 置为null，切断翻转区间和后续区间的联系
            end.next = null;
            //5. 反转，调用 reverse 方法反转反转区间的链表，并将反转后的链表连接到 pre 的后面
            pre.next = reverse(start);

            // 6. 连接后续节点
            //将start的后续节点指针指向next
            start.next = restNode;
            //7. 最后更新pre和end节点, 让他们重新指向反转区间后的末尾节点（即start）
            pre = start;
            end = start;
        }
        return dummy.next;
    }

    // 反转链表的方法, 返回第一个节点
    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur!= null){
            //保存下一个节点
            ListNode next = cur.next;
            //翻转
            //当前节点下一个节点指向前一个节点
            cur.next = prev;
            // 前一个节点后移为当前节点
            prev = cur;
            //当前节点后移到下一个节点
            cur = next;
        }

        return prev;
    }

}
